//
//  01_链表合并.swift
//  LeetCode
//
//  Created by Hao on 2020/6/22.
//  Copyright © 2020 Hao. All rights reserved.
//

import Foundation

struct MergeList {
    
    /// 21. 合并两个有序链表
    /// https://leetcode-cn.com/problems/merge-two-sorted-lists
    /// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    ///
    /// 示例：
    /// 输入：1->2->4, 1->3->4
    /// 输出：1->1->2->3->4->4
    static func twoSorted<E : Comparable>(list1: LinkedNode<E>?, list2: LinkedNode<E>?) -> LinkedNode<E>? {
        if list1 == nil || list2 == nil {
            return nil
        }
        
        var first = list1
        var second = list2
        var mergeList: LinkedNode<E>? = nil
        var resList = mergeList
        while first != nil || second != nil {
            if first == nil {
                mergeList?.next = second
                mergeList = mergeList?.next
                break
            }
            if second == nil {
                mergeList?.next = first
                mergeList = mergeList?.next
                break
            }
            if let e1 = first?.element, let e2 = second?.element {
                if e1 <= e2 {
                    if mergeList == nil {
                        mergeList = first
                        resList = mergeList
                    }
                    else {
                        mergeList?.next = first
                        mergeList = mergeList?.next
                    }
                    first = first?.next
                }
                else {
                    if mergeList == nil {
                        mergeList = second
                        resList = mergeList
                    }
                    else {
                        mergeList?.next = second
                        mergeList = mergeList?.next
                    }
                    second = second?.next
                }
            }
        }
        
        return resList
    }
    
}
